package class05;

/**
 * <a href="https://leetcode.cn/problems/count-of-range-sum/">327. 区间和的个数</a>
 */
public class Code01_CountOfRangeSum {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] sums = new long[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            sums[i] = sums[i - 1] + nums[i];
        }
        return process(sums, lower, upper, 0, sums.length - 1);
    }

    private int process(long[] sums, int lower, int upper, int L, int R) {
        if (L == R) {
            return sums[L] >= lower && sums[R] <= upper ? 1 : 0;
        }
        int M = L + ((R - L) >> 1);
        int l = process(sums, lower, upper, L, M);
        int r = process(sums, lower, upper, M + 1, R);
        int m = merge(sums, lower, upper, L, M, R);
        return l + r + m;
    }

    private int merge(long[] sums, int lower, int upper, int L, int M, int R) {
        int result = 0;
        int winL = L;
        int winR = L;
        for (int i = M + 1; i <= R; ++i) {
            long winLower = sums[i] - upper;
            long winUpper = sums[i] - lower;
            while (winR <= M && sums[winR] <= winUpper) {
                winR++;
            }
            while (winL <= M && sums[winL] < winLower) {
                winL++;
            }
            result += winR - winL;
        }
        long[] help = new long[R - L + 1];
        int i = 0;
        int l = L;
        int r = M + 1;
        while (l <= M || r <= R) {
            if (l > M) {
                help[i++] = sums[r++];
            } else if (r > R) {
                help[i++] = sums[l++];
            } else {
                help[i++] = sums[l] < sums[r] ? sums[l++] : sums[r++];
            }
        }
        System.arraycopy(help, 0, sums, L, help.length);
        return result;
    }
}
